package madixin.t109;


class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }
        ListNode preMid = getMid(head);
        TreeNode mid = new TreeNode(preMid.next.val);
        if (preMid.next.next != null) {
            mid.right = sortedListToBST(preMid.next.next);
        }
        preMid.next = null;//断开链表
        mid.left = sortedListToBST(head);

        return mid;
    }

    private ListNode getMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    /**
     * 先转数组
     */
    public TreeNode sortedListToBST2(ListNode head) {
        if (head == null) {
            return null;
        }
        int array[] = getListToArray(head);
        return makeBST(array, 0, array.length - 1);
    }

    private TreeNode makeBST(int[] array, int start, int end) {
        int mid = (start + end) / 2;
        TreeNode cur = new TreeNode(array[mid]);
        if (start < mid) {
            cur.left = makeBST(array, start, mid - 1);
        }
        if (mid < end) {
            cur.right = makeBST(array, mid + 1, end);
        }

        return cur;
    }

    private int[] getListToArray(ListNode head) {
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        int array[] = new int[length];
        for (int i = 0; i < length; i++) {
            array[i] = head.val;
            head = head.next;
        }
        return array;
    }
}